
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1839. -- 战争与和平
</title><center><h2>1839: 战争与和平
</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>2&nbsp;&nbsp;<span class=green>Solved: </span>2<br>[<a href='submitpage.php?id=1839'>Submit</a>][<a href='problemstatus.php?id=1839'>Status</a>][<a href='bbs.php?id=1839'>Discuss</a>]</center><h2>Description</h2><div class=content>很久很久以前，在那遥远的东方（其实好像一点都不远……），有两个伟大的帝王，他们分别是MJW和CRX。在华夏大地上，他们为了证明自己是最伟大的帝王、自己才是这片土地的主宰，进行了无数次伟大的战役。战争满足了两位帝王的野心，也给这片大地带来了无穷的灾难。MJW在这些战役中经常失败，渐渐地他也失去与之争霸的信心。在很多次战役后，他开始渴望和平，渴望宁静。但是他知道CRX是不会这么轻易罢休的，所以他决定修建万里长城来阻止战争的发生。华夏大地是由很多个洲组成的，从平面地图上看，每个州都是一个简单多边形。越过一个州的边界，要么进入别的州，要么就走出了华夏大地。而两个州的边界要么完全相同、要么没公共部分、要么只在端点处有公共部分。不会有一个州包含其它的州。MJW和CRX各有一个首都，他们的首都会唯一的属于一个州而不会在边界上。现在MJW就是要修建围墙将两人首都完全隔离，即围墙要么将MJW的首都包围起来，要么将CRX的首都包围起来。但是围墙是不能乱修的，如果将围墙修在一个州的内部，是会引起人民的公愤的。所以，MJW只能选择在边界上修建围墙。而且如果要在一条边界上修建，就必须完全修建，不能只修建一部分（好像修建一部分等于没修，我废话了……）。在每条边界上修建围墙都要一定的花费，不同的修建方案其代价也是不同的。所以MJW需要知道完成这项工程的最小代价是多少。不用说，你逃不掉了，这个任务还得交给你。
</div><h2>Input</h2><div class=content>输入文件的第一行包含一个整数m，表示不同的边界数目。
接下来m行，每行包含5个整数x1,y1,x2,y2，V，表示这个边界的两个端点分别是(x1,y1)和(x2,y2),在这条边界上修建围墙的代价为V。
接下来一行包含4个整数mx,my,cx,cy，表示MJW的首都位于(mx,my)，CRX的首都位于(cx,cy)。
</div><h2>Output</h2><div class=content>    输出一行仅包含一个整数，表示最小的代价。
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>13<br />
0 6 3 6 9 0 0 4 2 8<br />
4 4 6 6 7 2 4 3 6 1<br />
3 6 6 6 1 6 4 6 6 1<br />
4 2 6 4 1 0 0 0 6 6<br />
2 2 2 4 1 2 2 4 2 1<br />
0 6 2 4 5 2 4 4 4 4<br />
4 2 4 4 3<br />
3 3<br />
2 5<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>6<br />
<br />
对于100%的数据    m < = 3000  所有坐标的绝对值不超过10000<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=2008湖南省队集训By刘鹰'>2008湖南省队集训By刘鹰</a></p></div><center>[<a href='submitpage.php?id=1839'>Submit</a>][<a href='problemstatus.php?id=1839'>Status</a>][<a href='bbs.php?id=1839'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
